import Util.TreeNode;

import java.util.HashMap;

/**
 * 有先序遍历和中序遍历，重建二叉树
 */
public class Solution7 {

    HashMap<Integer, Integer> dic = new HashMap<>();
    int[] pre_list;

    public TreeNode reConstructBiTree(int[] preOrder, int[] inOrder){
        pre_list = preOrder;
        for (int i = 0; i < inOrder.length; i++)
            dic.put(inOrder[i], i);
        return recur(0, 0, inOrder.length - 1);
    }

    private TreeNode recur(int pre_root, int in_left, int in_right){
        if (in_left > in_right)
            return null;
        TreeNode root = new TreeNode(pre_list[pre_root]);
        int i = dic.get(pre_list[pre_root]);
        root.left = recur(pre_root + 1, in_left, i - 1);
        root.right = recur(pre_root + i - in_left + 1, i + 1, in_right);
        return root;
    }
}
